// 200.[并查集/没看懂swap] 岛屿数量
//  https://leetcode.cn/problems/number-of-islands/
// 复杂度：O(MN)
// 同样地，我们也可以使用并查集代替搜索。为了求出岛屿的数量，我们可以扫描整个二维网格。
// 如果一个位置为 11，则将其与相邻四个方向上的 11 在并查集中进行合并。
// 最终岛屿的数量就是并查集中连通分量的数目。
class UnionFind {
 public:
  UnionFind(vector<vector<char>>& grid) {
    count = 0;
    int m = grid.size();
    int n = grid[0].size();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == '1') {
          parent.push_back(i * n + j);
          ++count;
        } else {
          parent.push_back(-1);
        }
        rank.push_back(0);
      }
    }
  }
  int find(int i) {
    if (parent[i] != i) parent[i] = find(parent[i]);
    return parent[i];
  }
  void unite(int x, int y) {
    int rootx = find(x);
    int rooty = find(y);
    if (rootx != rooty) {
      if (rank[rootx] < rank[rooty]) {
        swap(rootx, rooty);
      }
      parent[rooty] = rootx;
      if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
      --count;
    }
  }
  int getCount() const { return count; }

 private:
  vector<int> parent;
  vector<int> rank;
  int count;
};
class Solution {
 public:
  int numIslands(vector<vector<char>>& grid) {
    int nr = grid.size();
    if (!nr) return 0;
    int nc = grid[0].size();
    UnionFind uf(grid);
    int num_islands = 0;
    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          grid[r][c] = '0';
          if (r - 1 >= 0 && grid[r - 1][c] == '1')
            uf.unite(r * nc + c, (r - 1) * nc + c);
          if (r + 1 < nr && grid[r + 1][c] == '1')
            uf.unite(r * nc + c, (r + 1) * nc + c);
          if (c - 1 >= 0 && grid[r][c - 1] == '1')
            uf.unite(r * nc + c, r * nc + c - 1);
          if (c + 1 < nc && grid[r][c + 1] == '1')
            uf.unite(r * nc + c, r * nc + c + 1);
        }
      }
    }
    return uf.getCount();
  }
};